package lib.combination;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * <b>Pick k objects out of n objects</b>
 * 
 * <pre>
 * For example, pick 3 cards from 7 cards. Each card is numbered from 0-6. Each
 * combination is unique if we make sure any number on the left is smaller than
 * numbers on the right. That is, if (i < j) then (a[i] < a[j]).
 * 
 * In the order of dictionary, the smallest one is {0,1,2}. The next one is
 * {0,1,3}, {0,1,4}, ... , {0,1,6}, {0,1,7}->{0,2,3}. The last one is {4,5,6},
 * which is also the only case that a[0]=4.
 * 
 * After such preparation, we are ready to enumerate all the combination.
 * </pre>
 * 
 * @author <a href="http://www.sureinterview.me">SureInterview</a>
 * 
 */
public class CombinationImpl<T extends Comparable<T>> extends Combination<T> {
	Integer combArr[]; // current combination
	CombUtil cu = new CombUtilImpl();

	int k; // pick k out of total n objects.

	int n; // total number
	Integer nextDigit[]; // next digit that is different from current digit.

	List<T> objList; // the object list

	/**
	 * Get the combination of "k" objects out of total "n" objects.
	 * 
	 * @param total
	 *            total number of objects.
	 * @param num
	 *            pick "num" objects out of the "total" number of objects.
	 */
	public CombinationImpl(List<T> obj, int num) {
		super();
		if (obj == null)
			throw new ExceptionInInitializerError("Invalid parameters.");

		// initialize
		objList = obj;
		this.n = obj.size();
		this.k = num;

		if (k <= 0 || n < k)
			throw new ExceptionInInitializerError("Invalid parameters.");

		// nextDigit[i]:next digit that is different from current digit.
		nextDigit = new Integer[n];
		nextDigit[n - 1] = n;
		for (int i = n - 2; i >= 0; i--) {
			if (objList.get(i + 1).compareTo(objList.get(i)) == 0) {
				nextDigit[i] = nextDigit[i + 1];
			} else {
				nextDigit[i] = i + 1;
			}
		}

		combArr = new Integer[k];
		reset();
	}

	/**
	 * get the combination by the 0-based index.
	 * 
	 * Follow the example, pick 3 cards from 7 cards, the smallest combination
	 * is {0,1,2}, next one is {0,1,3}.
	 * 
	 * Suppose we want to get the 19th combination. Because there are c(6,2)=15
	 * combinations that starts with 0, {0,*,*} and c(5,2)=10 combinations start
	 * with 1 {1,*,*}, the 19th combination must has pattern {1,*,*}. There are
	 * 4 combinations left. Follows the similar reasoning, the second digit is
	 * 2. (c(4,1)=4). So, the 19th combination = {1,2,6}.
	 * 
	 * @param index
	 *            the combination indicated by 0-based index.
	 * 
	 * @return the combination for valid index. Otherwise, null.
	 */
	@Override
	public List<T> get(Long index) {
		if (index < 0 || index > cu.c(n, k) - 1)
			return null;

		Long idx = index + 1; // idx: 1-based index.
		List<Integer> combArr = new ArrayList<Integer>(k);

		// val is the current value being processed.
		int val = 0;

		// scan from left to right
		outer: for (int curBit = 0; curBit < k; curBit++) {
			for (;;) {
				// calculation how many combinations if current val fills in
				// combArr[curBit]
				Long numCmb = cu.c(n - val - 1, k - curBit - 1);

				// current val just fits, nothing left.
				if (idx == numCmb) {
					// put val into the bit and fills remaining bits by largest
					// number.
					combArr.add(val);
					for (int i = curBit + 1; i < k; i++) {
						combArr.add(n - k + i);
					}
					break outer; // done
				}

				// idx should be further processed in right bits.
				if (idx < numCmb) {
					combArr.add(val++);
					break;
				}

				// idx passes numCmb, move to next val.
				idx -= numCmb;
				val++;
			}
		}

		// output the combination
		List<T> objComb = new ArrayList<T>(k);
		for (Integer i : combArr) {
			objComb.add(objList.get(i));
		}

		return objComb;
	}

	/**
	 * check if there are more combinations to enumerate.
	 */
	@Override
	public boolean hasNext() {
		return !combArr[0].equals(n - k); // curComb[0]
	}

	/**
	 * get the iterator
	 */
	@Override
	public Iterator<List<T>> iterator() {
		return this;
	}

	/**
	 * find the next combination
	 */
	@Override
	public List<T> next() {
		List<T> objComb = new ArrayList<T>(k);
		if (combArr[0] < 0) {
			combArr[0] = 0;
			for (Integer i : combArr) {
				objComb.add(objList.get(i));
			}
			return objComb;
		}

		/*
		 * 1. increment the last digit. But it is possible that the new value
		 * greater than n. So, we need to adjust it.
		 * 
		 * 2. adjust the carry over from right to left.
		 */

		// oflBit: bit needs to check for overflow.
		int oflBit = k - 1;

		// get the next number
		combArr[oflBit] = nextDigit[combArr[oflBit]];
		// sweep from right to left for overflow.
		for (; combArr[oflBit] > (n - (k - oflBit)); oflBit--) {
			combArr[oflBit - 1] = nextDigit[combArr[oflBit - 1]];
		}

		// filBit: make sure number on the left is smaller than number on the
		// right.
		int filBit = oflBit + 1;
		// adjust from left to right for smallest possible combination.
		for (; filBit < k; filBit++) {
			combArr[filBit] = combArr[filBit - 1] + 1;
		}

		// output the object combination
		for (Integer i : combArr) {
			objComb.add(objList.get(i));
		}

		return objComb;
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}

	/**
	 * initialize the combination array.
	 */
	public void reset() {
		combArr[0] = -1; // marker of first combination
		for (int i = 1; i < k; i++) {
			combArr[i] = i;
		}
	}
}
